#include <iostream>
#include <vector>

void backtrace(std::vector<bool> cols, std::vector<std::vector<bool>> state,
               std::vector<std::vector<std::vector<bool>>> &res,
               std::vector<bool> diagonal1, std::vector<bool> diagonal2,
               int row, int n) {
  // 最后一行已放入元素
  if (row == n) {
    res.push_back(state);
    return;
  }
  // 遍历列
  for (int col = 0; col < n; col++) {
    int pos1 = row - col + n - 1;
    int pos2 = row + col;
    if (!cols[col] && !diagonal1[pos1] && !diagonal2[pos2]) {
      state[row][col] = true;
      cols[col] = diagonal1[pos1] = diagonal2[pos2] = true;
      backtrace(cols, state, res, diagonal1, diagonal2, row + 1, n);
      // 回溯
      state[row][col] = false;
      cols[col] = diagonal1[pos1] = diagonal2[pos2] = false;
    }
  }
}

std::vector<std::vector<std::vector<bool>>> nQueens(int n) {
  // 对角线数量为 2*n - 1
  // 主对角线上所有元素 row-col相等[-n+1, n-1]
  // 次对角线上所有元素 row+col相等[0, 2n-2]
  std::vector<bool> diagonal1(2 * n - 1, false);
  std::vector<bool> diagonal2(2 * n - 1, false);
  std::vector<bool> cols(n, false);
  std::vector<std::vector<std::vector<bool>>> res;
  std::vector<std::vector<bool>> state(n, std::vector<bool>(n, false));

  backtrace(cols, state, res, diagonal1, diagonal2, 0, n);
  return res;
}
int main() {
  int n = 5;
  auto res = nQueens(n);
  for (auto &r : res) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        std::cout << r[i][j] << " ";
      }
      std::cout << std::endl;
    }
    std::cout << "----------------------------\n";
  }

  return 0;
}